The representation of surfaces through subdivision elegantly addresses many of the drawbacks that are inherent in conventional 3D shape representations. Subdivision offers an efficient and compact technique to represent the geometry with minimal connectivity information. The use of subdivision beneficially: (i) generalizes the classical spline patch approach to arbitrary topology; (ii) naturally accommodates multiple levels of detail; and (iii) produces meshes with well-shaped elements arranged in almost regular structures, suitable for digital processing.
One of the earliest approaches to the multiresolution analysis of arbitrary meshes was proposed by M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle, Multiresolution Analysis of Arbitrary Meshes, Computer Graphics, vol. 29: Annual Conference Series, pps.173–182, 1995. In this case, domain decomposition is done by randomly selecting seeds on the 3D model around which tiles are grown. The growth of a tile is driven by a set of topological criteria, and does not take into account the shape of the surface.
L. Kobbelt. J. Vorsatz, U. Labsik and H-P. Seidel described in A Shrink Wrapping Approach to Remeshing Polygonal Surface, Computer Graphics Forum (Eurographics'99), vol. 18(3):119–130, The Eurographics Association and Blackwell Publishers, ed. P. Brunet and R. Scopigno, 1999, a shrink-wrapping approach to semi-regular mesh extraction. The approach, however, is limited to closed genus 0 input meshes.
A parameterization-based approach to finding a suitable base domain is described by U. Labsik, K. Hormann, and G. Greiner, Using Most Isometric Parameterizations for Remeshing Polygonal Surfaces, Proceedings of Geometric Modeling and Processing 2000, pps. 220–228 (IEEE Computer Society Press). This method is restricted to manifolds with boundary and no holes, and it is insensitive to shape variations.
T. Kanai in MeshToSS: Converting Subdivision Surfaces from Dense Meshes, Proceedings of Modeling and Visualization 2001, IOS Press, Amsterdam, pps. 325–332, 2001, describes a method to recover a multiresolution Loop subdivision surface. The construction of the base domain is based on simplification of the input mesh which is presumed to be dense. Some surface information such as sharp features are used to guide the simplification process. Nevertheless, like any simplification-based approach, there is limited flexibility as to where vertices of the base domain are positioned and the simplification process may be quite time-consuming. Moreover, no multiresolution hierarchy is directly extracted, rather, different base meshes are used to lead to different approximations.
Of more interest to this invention is the approach of Alliez et al. (P. Alliez, M. Meyer, and M Desbrun, Interactive Geometry Remeshing, ACM Transactions on Graphics. Special issue for SIGGRAPH conference, 21(3):347–354, 2002). In this case, various property maps are computed for a mesh and used for remeshing. The maps, however, correspond to mesh charts with disk topology, and they are not used to compute the decomposition into charts, which is done using the method proposed by M. Eck, et al., Multiresolution Analysis of Arbitrary Meshes, Computer Graphics, vol. 29: Annual Conference Series, pps.173–182, 1995.
Other methods attempt to recover semi-regular meshes from other types of input data. For example, given as input a signed distance volume, the method of Z. Wood, P. Schroder, D. Breen, and M. Desbrun, Semi-regular mesh extraction from volumes, IEEE Visualization, pps. 275–282, 2000, is directed towards the extraction of semi-regular iso-surfaces from volumes. Wood et al. proceed by building a coarse domain for the isosurface by stitching together contours on the surface. This approach is driven by topological information about the model extracted from the volume dataset, and does not include any surface properties in the computation of the base domain. It is also restricted to closed meshes (i.e., meshes with no boundary). Also starting from a volume, K. Hormann, U. Labsik, M. Meister, and G. Greiner, Hierarchical Extraction of Iso-Surfaces with Semi-Regular Meshes, Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications, pps. 53–58, 2002, K. Lee and N. M. Patrikalakis editors (ACM Press), describe a process of semi-regular mesh extraction. The base mesh is computed using a standard Marching Cubes algorithm (W. Lorensen and H. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of SIGGRAPH 87, pps. 163–169, 1987), with no regard for surface properties.
A cloud of points is another, relatively common data representation, typically generated by scanning devices. Fitting surfaces to clouds of points has been extensively studied. For example, reference can be made to H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald. J. Schweitzer, and W. Stuetzle, Piecewise Smooth Surface Reconstruction, Computer Graphics, Proceedings of SIGGRAPH 94, vol. 28:295–302, Annual Conference Series, 1994, where the authors describe an optimization-based method for fitting a piecewise smooth surface to a dense set of points. The approach is very compute-intensive as it involves several optimization steps. Also, the recovered mesh is at a single resolution and the method is not applicable to sparse data sets. Mention may also be made of the approach of Suzuki et al. (H. Suzuki, S. Takeuchi, T. Kanai, and F. Kimura, Subdivision Surface Fitting to a Range of Points, Proceedings IEEE Pacific Graphics 99, pps. 158–167, 1999), which recovers meshes with subdivision connectivity. However, this approach requires a manual outlining of the base mesh.
A significant drawback to representing surfaces using semi-regular meshes is having to convert existing 3D data to this format. Current 3D content creation technology typically leads to either irregular representations, such as point clouds and arbitrary polygonal meshes, or to regular but constrained representations, such as spline patches. While volumetric datasets are typically regular in nature, most extraction algorithms tend to yield an irregular mesh from a volumetric dataset.
What is thus required is a technique for the conversion of arbitrary polygonal meshes to multiresolution subdivision hierarchies. While no standard has yet emerged for 3D shape description, polygonal meshes are the output representation of choice in many applications, especially in the final stages of processing for viewing and rendering purposes. Many methods have been devised to generate arbitrary meshes from other representations.
The task of converting an arbitrary mesh to one with semi-regular connectivity can be viewed as having two main steps: (a) identifying a suitable parameterization domain for the input mesh; and (b) resampling the original geometry at regularly-spaced intervals in parameter space.
By far, the first step is the most challenging one. An ideal domain should have several properties. As examples, an ideal domain will have the properties of: a small number of elements; elements that are well-shaped polygons, with reasonable aspect ratios; and that partition the surface of the model into a collection of height-field patches suitable for resampling. Once a parameterization of the model is found, a multiresolution representation can be extracted by choosing the resolution of the finest level, resampling on this level, and then applying multiresolution analysis to generate a hierarchy of details at intermediate levels.
Methods that have attempted to address this problem typically involve some degree of manual adjustment, or they generate arbitrary domains, by simplification of the original mesh.
With specific regard to domain decomposition, it is noted that parameterization of discrete surfaces plays an important role in many computer graphics applications. A commonly used technique to define a parameterization is to identify a coarse polyhedral domain that approximates the surface, and to then define the parameterization as a function over this domain. The first task, domain identification or, alternatively, model decomposition, has numerous applications beyond parameterization generation, in areas such as object recognition, shape perception, collision detection and ray tracing.
To summarize the foregoing, it has been shown that subdivision methods lead to hierarchical representations of 3D surface data that are useful in many applications from network transmission to surface styling and design. A number of algorithms that exploit their semi-regular nature have recently emerged and address some of the major limitations posed by more traditional surface representations, such as arbitrary polygonal meshes and NURBS, in an elegant and efficient way. However, an obstacle to the widespread acceptance of these newer algorithms is the lack of a general, high-quality conversion method from other 3D data formats.
What is thus needed, and what is therefore a goal of this invention to provide, is a method to perform the automatic conversion of arbitrary polygonal meshes into multiresolution hierarchies having subdivision connectivity.